package leetcode.dp;


/**
 * 面试题 17.16. 按摩师
 */
public class Message {
    public int massage(int[] nums) {
        int len = nums.length;
        int[] tmp = new int[len];
        if (len == 0) {
            return 0;
        } else if (len == 1) {
            return nums[0];
        } else if (len == 2) {
            return Math.max(nums[0], nums[1]);
        } else if (len == 3) {
            return Math.max(nums[0] + nums[2], nums[1]);
        } else {
            tmp[0] = nums[0];
            tmp[1] = Math.max(nums[0], nums[1]);
            tmp[2] = Math.max(nums[0] + nums[2], nums[1]);
            for (int i = 3; i < len; i++) {
                tmp[i] = Math.max(tmp[i - 2] + nums[i], tmp[i - 3] + nums[i]);
            }
            return Math.max(tmp[len - 2], tmp[len - 1]);
        }
    }
}
